package 链表.middle;

/**
 * 删除链表的倒数第N个节点
 * @author Lw中
 * @date 2020/9/23 14:29
 */
public class ShiJiu {

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 使用双指针方法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /* p指针先往前走n个节点 */
        ListNode p = head;
        /* q节点等p节点完成了n个节点的长度后再和p节点一起走，直到p节点为空 */
        ListNode q = head;
        /* p节点先走n个节点 */
        for (int i = 0; i < n; i++) {
            p = p.next;
        }
        if (p == null) {
            head = head.next;
            return head;
        }
        /* p、q同时走p剩下未走的节点 */
        while (p.next != null) {
            p = p.next;
            q = q.next;
        }
        q.next = q.next.next;
        /* 返回头结点 */
        return head;
    }

    public static void main(String[] args) {

    }

}
